Enterprise Database Systems
Graph Data Structures and Algorithms
Graph Data Structures: Implementing Graph Traversal & Shortest Path Algorithms
it_dagdsadj_03_enus
Graph Data Structures: Representing Graphs Using Matrices, Lists, & Sets
it_dagdsadj_02_enus
Graph Data Structures: Understanding Graphs & Knowledge Graphs
it_dagdsadj_01_enus
Graph Data Structures: Implementing Graph Traversal & Shortest Path Algorithms
Lesson Objectives
Graph Data Structures: Implementing Graph Traversal & Shortest Path Algorithms
- discover the key concepts covered in this course
- recall how depth-first and breadth-first traversal works
- implement breadth-first traversal using a queue data structure
- implement depth-first traversal using a stack, as well as using recursion
- compute the shortest path in an unweighted graph using breadth-first traversal and the distance table
- implement the shortest path algorithm for an unweighted graph
- recall the properties of greedy algorithms
- list the relaxation techniques used to populate the distance table in Dijkstra's algorithm
- compute the shortest path in a weighted graph using greedy traversal and the distance table
- implement Dijkstra's algorithm to compute the shortest path in a weighted graph
- summarize the key concepts covered in this course
Overview/Description
What makes the graph data structure very interesting and powerful is the large number of algorithms that can be run on graphs to extract insights. Common graph algorithms include traversing a graph and computing the shortest path between nodes. Implementing these algorithms is a great way to learn how graphs are explored and optimized. In this course, learn how graphs can be traversed by studying both depth-first and breadth-first graph traversal and discover how they can be implemented using a stack and a queue respectively. Next, explore how to compute the shortest path in an unweighted graph. And finally, use Dijkstra’s algorithm to compute the shortest path in a weighted graph. Upon completion of this course, you will be able to implement optimal algorithms on graphs.
What makes the graph data structure very interesting and powerful is the large number of algorithms that can be run on graphs to extract insights. Common graph algorithms include traversing a graph and computing the shortest path between nodes. Implementing these algorithms is a great way to learn how graphs are explored and optimized. In this course, learn how graphs can be traversed by studying both depth-first and breadth-first graph traversal and discover how they can be implemented using a stack and a queue respectively. Next, explore how to compute the shortest path in an unweighted graph. And finally, use Dijkstra’s algorithm to compute the shortest path in a weighted graph. Upon completion of this course, you will be able to implement optimal algorithms on graphs.
Target
Prerequisites: none
Graph Data Structures: Representing Graphs Using Matrices, Lists, & Sets
Lesson Objectives
Graph Data Structures: Representing Graphs Using Matrices, Lists, & Sets
- discover the key concepts covered in this course
- model graphs using a square adjacency matrix to represent nodes and edges
- represent graphs using an adjacency matrix in Python
- represent different graph types - directed, undirected, weighted, and unweighted using adjacency matrices
- model graphs using an adjacency list and adjacency set and compare the two representations
- represent graphs using an adjacency list in Python
- represent graphs using an adjacency set in Python
- summarize the key concepts covered in this course
Overview/Description
In order to really understand how graphs work, it is important to know how they are implemented. There are multiple ways to represent graphs in code and each representation has its own advantages and disadvantages. In this course, you will implement graphs using three different representations - the adjacency matrix, the adjacency list, and the adjacency set. Learn how the adjacency matrix representation uses a square matrix to represent connections between the nodes of a graph and also edge weights. Next, explore how the adjacency list suffers from a major drawback: the same graph can have multiple representations. Finally, discover how the adjacency set representation has exactly one way in which a graph is represented. When you are finished with this course, you will be able to create and work with your own graph structures and optimize them for different purposes.
In order to really understand how graphs work, it is important to know how they are implemented. There are multiple ways to represent graphs in code and each representation has its own advantages and disadvantages. In this course, you will implement graphs using three different representations - the adjacency matrix, the adjacency list, and the adjacency set. Learn how the adjacency matrix representation uses a square matrix to represent connections between the nodes of a graph and also edge weights. Next, explore how the adjacency list suffers from a major drawback: the same graph can have multiple representations. Finally, discover how the adjacency set representation has exactly one way in which a graph is represented. When you are finished with this course, you will be able to create and work with your own graph structures and optimize them for different purposes.
Target
Prerequisites: none
Graph Data Structures: Understanding Graphs & Knowledge Graphs
Lesson Objectives
Graph Data Structures: Understanding Graphs & Knowledge Graphs
- discover the key concepts covered in this course
- use graph nodes and edges to model entities and relationships in the real world
- recall the attributes of the property graph model used to represent knowledge graphs
- compare and contrast plain old graphs with knowledge graphs
- create taxonomies and ontologies by using higher-level organizing principles with knowledge graphs
- list the different types of graphs and explore their structure
- create, manipulate, and visualize graphs in NetworkX
- perform common graph operations to compute adjacent nodes, degree of a node, and check edge connections on undirected graphs
- perform common graph operations to find predecessors, successors, ancestors, and descendants on directed graphs
- execute algorithms in NetworkX to compute triangle count, simple cycles in graphs, and test for a directed acyclic graph
- execute algorithms in NetworkX to perform topological sort, compute the shortest path, and find the minimal spanning tree
- summarize the key concepts covered in this course
Overview/Description
Graphs are used to model a large number of real-world scenarios, including professional networks, flight networks, and schedules. Working in these problem domains involves a deep understanding of how graphs are represented and how graph algorithms work. Learn the basic components of a graph and how nodes and edges can be used to model relationships. Examine how domains such as social networks, purchases on an e-commerce platform, and connected devices can be modeled using graphs. Next, explore how to use an organizing principle to add semantic meaning and context to graphs. Discover how to apply higher-level organizing principles to knowledge graphs using taxonomies and ontologies. Finally, get hands-on experience creating and manipulating graphs, and running graph algorithms using the NetworkX library in Python. When you have completed this course, you will have a solid understanding of how graphs model entities and relationships in the real world.
Graphs are used to model a large number of real-world scenarios, including professional networks, flight networks, and schedules. Working in these problem domains involves a deep understanding of how graphs are represented and how graph algorithms work. Learn the basic components of a graph and how nodes and edges can be used to model relationships. Examine how domains such as social networks, purchases on an e-commerce platform, and connected devices can be modeled using graphs. Next, explore how to use an organizing principle to add semantic meaning and context to graphs. Discover how to apply higher-level organizing principles to knowledge graphs using taxonomies and ontologies. Finally, get hands-on experience creating and manipulating graphs, and running graph algorithms using the NetworkX library in Python. When you have completed this course, you will have a solid understanding of how graphs model entities and relationships in the real world.
Target
Prerequisites: none
